import java.util.Arrays;
import java.util.List;

/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-08 9:30 星期三
 * @motto the harder, the luckier。
 *
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 *
 * 返回这三个数的和。
 *
 * 假定每组输入只存在恰好一个解。
 * Completed at @date: 2024-05-08 10:52
 */

public class _16_ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        for(int i=0;i<nums.length;i++) {
            int start = i+1, end = nums.length - 1;
            while(start < end) {
                //计算当前三元组的总和 sum = nums[start] + nums[end] + nums[i]。
                //如果当前的 sum 与 target 的距离小于现有答案与 target 的距离，那么更新 ans。
                //根据 sum 与 target 的大小关系，调整指针：
                //如果 sum > target，说明需要减少 sum 的大小，所以 end--。
                //如果 sum < target，则需要增加 sum 的大小，所以 start++。
                //如果 sum == target，则直接返回 ans，因为此时已经找到了最接近的三元组。
                int sum = nums[start] + nums[end] + nums[i];
                if(Math.abs(target - sum) < Math.abs(target - ans))
                    ans = sum;
                if(sum > target)
                    end--;
                else if(sum < target)
                    start++;
                else
                    return ans;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        _16_ThreeSumClosest solution = new _16_ThreeSumClosest();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        int result = solution.threeSumClosest(nums, 4);
        System.out.println(result);

    }
}
